#include <bits/stdc++.h>
using namespace std;

/*
2616. 最小化数对的最大差值
已解答
中等
相关标签
premium lock icon
相关企业
提示
给你一个下标从 0 开始的整数数组 nums 和一个整数 p 。请你从 nums 中找到 p 个下标对，每个下标对对应数值取差值，你需要使得这 p 个差值的 最大值 最小。同时，你需要确保每个下标在这 p 个下标对中最多出现一次。

对于一个下标对 i 和 j ，这一对的差值为 |nums[i] - nums[j]| ，其中 |x| 表示 x 的 绝对值 。

请你返回 p 个下标对对应数值 最大差值 的 最小值 。

 

示例 1：

输入：nums = [10,1,2,7,1,3], p = 2
输出：1
解释：第一个下标对选择 1 和 4 ，第二个下标对选择 2 和 5 。
最大差值为 max(|nums[1] - nums[4]|, |nums[2] - nums[5]|) = max(0, 1) = 1 。所以我们返回 1 。
示例 2：

输入：nums = [4,2,1,2], p = 1
输出：0
解释：选择下标 1 和 3 构成下标对。差值为 |2 - 2| = 0 ，这是最大差值的最小值。
 

提示：

1 <= nums.length <= 105
0 <= nums[i] <= 109
0 <= p <= (nums.length)/2
*/

// 法一
class Solution {
public:
    int minimizeMax(vector<int>& nums, int p) {
        // 先排序数组  差值小 方便找最小化最大差值 数对
        if (p == 0) return 0;

        sort(nums.begin(), nums.end());
        int n = nums.size();
        // 左右指针 用于二分查找
        int left = 0, right = nums.back() - nums.front();
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (canFormPairs(nums, p, mid))     right = mid;
            else    left = mid + 1;
        }
        return left;
    }

    // 贪心再做个验证​​
    bool canFormPairs(const vector<int>& nums, int p, int maxDiff) {
        int count = 0;
        for (int i = 0; i < nums.size() - 1 && count < p; ) {
            if (nums[i + 1] - nums[i] <= maxDiff){
                count++;
                i += 2;     // 要跳过下一个元素 已经形成一个数对了
            } else  
                i++; 
        } 
        
        return count >= p;
    }
};


// 法二
class Solution {
public:
    int minimizeMax(vector<int>& nums, int p) {
        // 先排序数组  差值小 方便找最小化最大差值 数对
        if (p == 0) return 0;

        sort(nums.begin(), nums.end());
        int n = nums.size();
        // 左右指针 用于二分查找
        int left = 0, right = nums.back() - nums.front();
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (canFormPairs(nums, p, mid))     right = mid;
            else    left = mid + 1;
        }
        return left;
    }

    // dp 动态规划来验证  感觉不如贪心​​
    bool canFormPairs(const vector<int>& nums, int p, int maxDiff) {
        int n = nums.size();
        vector<int> dp(n, 0);

        for (int i = 1; i < n; i++) {
            if (nums[i] - nums[i - 1] <= maxDiff) {
                if (i >= 2)     dp[i] = max(dp[i - 2] + 1, dp[i - 1]);
                else        dp[i] = 1;
            } else  dp[i] = dp[i - 1];

            if (dp[i] >= p)     return true;
        }
        return dp.back() >= p;
    }
};